#include <stdio.h>
#include <stdlib.h>

#define ERROR NULL
#define false 0
#define true 1

typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

List MakeEmpty(); 
Position Find( List L, ElementType X );
bool Insert( List L, ElementType X, Position P );
bool Delete( List L, Position P );

int main()
{
    List L;
    ElementType X;
    Position P;
    int N;
    bool flag;

    L = MakeEmpty();
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &X);
        flag = Insert(L, X, L->Next);
        if ( flag==false ) printf("Wrong Answer\n");
    }
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &X);
        P = Find(L, X);
        if ( P == ERROR )
            printf("Finding Error: %d is not in.\n", X);
        else {
            flag = Delete(L, P);
            printf("%d is found and deleted.\n", X);
            if ( flag==false )
                printf("Wrong Answer.\n");
        }
    }
    flag = Insert(L, X, NULL);//此步操作是在队尾插入元素
    if ( flag==false ) printf("Wrong Answer\n");
    else
        printf("%d is inserted as the last element.\n", X);
    P = (Position)malloc(sizeof(struct LNode));//如何确定此时P的地址呢？0xb63c70 为什么会是这个？L地址？错了随机地址插不进去！
    flag = Insert(L, X, P);
    if ( flag==true ) printf("Wrong Answer\n");
    flag = Delete(L, P);
    if ( flag==true ) printf("Wrong Answer\n");
    for ( P=L->Next; P; P = P->Next ) printf("%d ", P->Data);
    system("pause");
    return 0;
}

List MakeEmpty() {
    //思路：创建一个空表头，指针域赋空，返回指针L
    List L = (struct LNode *)malloc(sizeof(struct LNode));
    L->Next = NULL;
    return L;
}

Position Find( List L, ElementType X ) {
    //思路：链表只能从第一个开始找，设置游离指针p 依次遍历各个元素并将其与X作比较 
    //特殊情况该如何处理？ 比如没有找到 返回ERROR 
    PtrToLNode p = L;
    for (; p; p = p->Next) {
        if (p->Data == X)
        return p; //返回他的当前元素的位置
    }
    return ERROR;
}

bool Insert( List L, ElementType X, Position P ) {
    //思路： 插入之前先创建结点 填入数据，然后插入在指定位置之前
    PtrToLNode NewNode = (struct LNode *)malloc(sizeof(struct LNode));
    NewNode->Data = X;

    Position prePoint = L;
    for (; prePoint; prePoint = prePoint->Next) {
        if (prePoint->Next == P) {
            // 也可以写成 NewNode->Next = P; 下列插入写法是模版写法，更好记忆，降低学习成本
            NewNode->Next = prePoint->Next;
            prePoint->Next = NewNode;

            return true;
        }
    }
        printf("Wrong Position for Insertion\n");
        return false;    
}

bool Delete( List L, Position P )  {
    //思路：通过一个指针完成删除 不合理的位置？ 
    PtrToLNode prePoint = L;
    for (; prePoint; prePoint = prePoint->Next) {
        if (prePoint->Next == P && prePoint->Next) {
            //此处感觉应该考虑P为NULL的情况，不知道有没有多余 欢迎指正
            prePoint->Next = P->Next;
            free(P);//释放空间
            return true;
        }
    }
    printf("Wrong Position for Deletion\n");
        return false;
}